package 题组;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 挚爱之夕
 * @date 2021/9/8 - 09 - 08 - 11:10
 * @Description: 题组
 * @Version: 1.0
 */
public class _005_数组中找两数的和为指定值 {
    //数组是非递减排序的，返回的是数组元素下标加一，即是第几个数
    public static void main(String[] args) {
        int[] a = new int[]{0,1,0,3,12};
        int[] ans = new int[2];
        ans=twoSum3(a,4);
        System.out.println(Arrays.toString(ans));
    }
    //哈希表
    private static int[] twoSum(int[] numbers, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(numbers[0],0);
        for(int i =1;i<numbers.length;i++){
            int another = target-numbers[i];
            if(map.containsKey(another)){
                int l = map.get(another);
                return new int[]{l+1,i+1};
            }
            map.put(numbers[i],i);
        }
        throw new IllegalArgumentException();
    }
    /*
    双指针：
    时间复杂度：O(n)，其中n是数组的长度。两个指针移动的总次数最多为n次。
    空间复杂度：O(1)。
     */
    public static int[] twoSum1(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
    /*
    二分查找：
    时间复杂度：O(nlogn)，其中n是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，
    寻找第二个数使用二分查找，时间复杂度是O(logn)，因此总时间复杂度是O(nlogn)。
    空间复杂度：O(1)。
     */
    public static int[] twoSum2(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
    //暴力法:O(N*N)
    private static int[] twoSum3(int[] numbers, int target){
        for (int i = 0; i < numbers.length-1; i++) {
            int another = target - numbers[i];
            for(int j = i+1;j< numbers.length;j++){
                if(numbers[j]==another){
                    return new int[]{i+1,j+1};
                }
            }
        }
        return new int[]{-1, -1};
    }
}
